考題日期:2015/12/22
題號:10533
星等:3
語言:C++

題目:

題意:
digit prime是一個質數，且其中的每個數的和也是質數。例如：41 是一個digit prime，因為 4+1=5，而 5 也是一個質數。17 就不是一個digit prime，因為 1+7=8，而 8 並不是質數。找出一定的範圍內有多少個 digit prime。

程式:

#include <iostream>
#include <math.h>
#include <stdio.h>
#define Size 1000000
using namespace std;
int prime[1000000] = {0};
int main()
{
    prime[0] = prime[1] =  1;
    for(int i = 2 ; i < sqrt(Size) ; i++)
    {
        if(!prime[i])
            for(int j = i + i ; j < Size ; j += i)
                prime[j] = 1;
    }
    int test,a,b;
    scanf("%d", &test);
    while(test--)
    {
        int digitprime = 0;
        scanf("%d%d", &a,&b);
        for(int i = a ; i <= b ; i++)
        {
            if(!prime[i])
            {
                int all = 0,k = i;
                while(k>0)
                {
                    all += k % 10;
                    k /= 10;
                }
                if(!prime[all])
                    digitprime++;
            }
        }
        printf("%d\n", digitprime);
    }
    return 0;
}

測資: